package pri.zjy.dynamicProgramming;

/**
 * @author zhangjy
 * @description 买卖股票的最佳时机
 * @date 2025/5/29 11:38
 */
public class MaxProfit_121 {

    public static void main(String[] args) {
        MaxProfit_121 maxProfit121 = new MaxProfit_121();

//        int[] prices = {7, 6, 4, 3, 1};
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit121.maxProfit(prices));
    }

    /**
     * 官解：一次遍历
     * <p>
     * 思路：只买卖一次股票，所以考虑在股票最低点买入股票，然后卖出即可。
     * 只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱，从而记录最大利润
     */
    public int maxProfit4(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            // 记录当前股票最低点
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            }
            // 当天卖出的利润
            int profit = prices[i] - minPrice;
            maxProfit = Math.max(maxProfit, profit);
        }

        return maxProfit;
    }

    /**
     * 个人：参照dmsxl
     */
    public int maxProfit3(int[] prices) {
        // 1.定义dp[i][2]
        // 第 i 天持有，或未持有股票的最大利润（0-未持有，1-已持有）
        // dp[i][0]第i天 未持有 股票的最大利润（第i-1天未持有，或者第i天才卖出）
        // dp[i][1]第i天 持有 股票的最大利润（第i-1天已持有，或者第i天才买入）
        int[][] dp = new int[prices.length][2];
        // 2.递推公式
        // 第i天未持有：Math.max(dp[i-1][0], dp[i-1][1]+prices[i])
        // 第i天持有：Math.max(dp[i-1][1], -prices[i])
        // 3.初始化
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        // 4.遍历
        // 从前往后
        for (int i = 1; i < prices.length; i++) {
            // 第i天未持有
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 第i天持有
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }

        return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][1]);
    }

    /**
     * dmsxl：dp-二维dp数组
     * <p>
     * 分析：
     * 股票只能买卖一次，求最大利润。
     * <p>
     * 为什么用二维dp数组？
     * ——若用一维数组，很难表示第 i 天，股票的持有状态；而使用二维，可以dp[i][0]表示持有股票的最大金额，dp[i][1]表示不持有股票的最大金额
     * <p>
     * 第 i 天持有股票，可能是前面某一天就买入了该股票，只是到第 i 天还没卖出；也可能是第 i 天才买入。
     * 同理，第 i 天不持有股票，可能前面就卖出了股票，到第 i 天还没重新买入；也可能是第 i  天才卖出。
     */
    public int maxProfit2(int[] prices) {

        // 1.dp[i][0]——第 i 天持有股票的最大利润（可能第i天才买入，也可能前面就买入）；dp[i][1]——第 i 天不持有股票的最大利润（可能第i天才卖出，也可能前面就卖出）；
        int[][] dp = new int[prices.length][2];

        // 2.递推公式
        // 1）dp[i][0]和dp[i-1][]的关系，即第i天持有
        // 若第i天前，已经买入该股票，则dp[i][0]=dp[i-1][0]
        // 反之，第i天才买入股票，那么dp[i][0]= -prices[i]
        // 为什么不是dp[i][0]=dp[i-1][0] - prices[i]，而直接等于 -prices[i]？——因为这里股票只能买卖一次，所以第i天买入，只需要扣减一次prices[i]。
        // 那么，第i天持有的最大利润就是dp[i][0] = Math.max(dp[i-1][0], - prices[i])
        // 2）dp[i][1]和dp[i-1][]的关系，即第i天不持有
        // 若第i天前，就已经卖出股票，则dp[i][1]=dp[i-1][1]
        // 反之，第i天才卖出股票，那么dp[i][1]=dp[i-1][0] + prices[i]；
        // 为什么不是dp[i][1]=dp[i-1][1] + prices[i] - prices[i-1]？——因为，第i天卖出，表明第i-1天是持有状态，然后再加上prices[i]即可；若第i-1天已经卖出，则直接等于dp[i-1][1]。

        // 那么，第i天不持有的最大利润就是dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i])

        // 3.初始化
        // dp[1][]可以由dp[0][]推导出
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        // 4.遍历
        // 从前往后
        for (int i = 1; i < prices.length; i++) {
            // 第i天持有
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            // 第i天不持有
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }

        return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][1]);
    }

    /**
     * 个人解法：dp
     * <p>
     * 超时！！！
     * <p>
     * 超时原因：一维dp数组，相当于暴力解法。
     */
    public int maxProfit(int[] prices) {
        // 1.dp[i]，表示第 i 天卖出股票获取的最大利润
        int[] dp = new int[prices.length];

        // 2.递推公式
        // dp[i]=Math.max(dp[i-1]+prices[i]-prices[i-1]

        // 3.初始化
        dp[0] = 0;

        // 4.遍历
        // 两层遍历，dp[i]依赖于前面每一项
        // 初始化dp[i]=0
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            dp[i] = 0;
            //从i向前遍历（[0,i-1]），记录最大利润；如若prices[i]>prices[i-1]，表明dp[i-1]可以在第i天卖出，则dp[i]=Math.max(dp[i-1]+prices[i]-prices[i-1], dp[i])；
            for (int j = i - 1; j >= 0; j--) {
                if (prices[i] > prices[j]) dp[i] = Math.max(dp[j] + prices[i] - prices[j], dp[i]);
            }
            maxProfit = Math.max(maxProfit, dp[i]);
        }

        return maxProfit;
    }

}
